/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
   
    struct ListNode* reverseList(struct ListNode* head)
{
       struct ListNode* cur =head;
       struct ListNode*rhead =NULL;
       
       while(cur)
       {
          struct ListNode*next =cur->next;
           //头插

           cur->next =rhead;
           rhead =cur;
           
           cur =next;
       }
       return rhead;
}
   
    bool chkPalindrome(ListNode* A) 
    {
        // 1.先用快慢指针找出中间位置
         
         ListNode*cur =A;
         ListNode*tail =A;
    
         while(tail && tail->next)
         {
             cur=cur->next;
             tail = tail->next->next;
         }
        
         //翻转
          ListNode*sur = reverseList(cur);      
         
         //比较
         while(A&&sur)
         {
             if(A->val != sur->val)
             {
                 return false;
             }
             A=A->next;
             sur=sur->next;
         }
          return true;
             

    }
};